package leetcode.stack_queue;

import javafx.util.Pair;

import java.util.*;

/**
 * 102. 二叉树的层序遍历
 * <p>
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 * <p>
 * <p>
 * <p>
 * 示例：
 * 二叉树：[3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * <p>
 * 返回其层次遍历结果：
 * <p>
 * [
 * [3],
 * [9,20],
 * [15,7]
 * ]
 * <p>
 * 层序遍历：广度遍历，使用队列进行辅助
 */
public class Solution102 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        //使用pair配对 进行记录当前节点，以及他处于的层级
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList();
        queue.add(new Pair<>(root, 0));
        while (!queue.isEmpty()) {
            //先出队，然后左孩子进队，右孩子进队
            Pair<TreeNode, Integer> pair = queue.remove();
            TreeNode node = pair.getKey();
            Integer level = pair.getValue();

            if (level == res.size()) {//说明该层级上没有进行遍历，list 为null
                res.add(new ArrayList<>());//进行创建
            }
            if (level < res.size()) {
                //进行添加元素
                res.get(level).add(node.val);
            }
            //左孩子，右孩子入队
            if (node.left != null)
                queue.add(new Pair<>(node.left, level + 1));
            if (node.right != null)
                queue.add(new Pair<>(node.right, level + 1));

        }
        return res;
    }
}
